#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int n, a[2005], dp[2005], pre[2005], nxt[2005];
void solve() {
    cin >> n;
    memset(nxt, 0x3f, sizeof nxt);
    memset(dp, -1, sizeof dp); dp[0] = 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (__gcd(a[i], a[j]) != 1) {
                nxt[j] = min(nxt[j], i);
                pre[i] = max(pre[i], j);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        int mn = 1e9;
        for (int j = i; j >= 1; j--) {
            if (nxt[j] > i) mn = min(mn, pre[j]);
            else if (mn >= j && dp[j - 1] != -1) dp[i] = max(dp[i], dp[j - 1] + 1);
        }
    } cout << dp[n] << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

